Many phenomena in reality can be properly abstracted into network traffic models in which the nodes and links represent actors and their interactions, respectively.^[1] For example, the data transmission via the Internet,^[2] the transferring of goods between entrepots, the flight between airports,^[3] and the cycle of carbon in ecosystems. The study of complex networks has been receiving a great deal of attention for many years.^[4,5] One of the main reasons for studying complex networks is to improve the efficiency of network transportation,^[6] in this regard, one method is to study the impact of the structure of the network, for example, research on the structure of aviation networks,^[3,7,8] and the other is to optimize the algorithm.^[9] Over the years, the dynamic process of complex networks^[10] has always attracted scholars’ attention. The topological properties of the network (e.g., degree distribution, average path length and clustering) have an important impact on the dynamic processes on the network. However, there are still many challenging topics to be improved, including traffic congestion,^[11] cascade failures,^[12] epidemic spreading,^[13] synchronization,^[14] and compressed sensing.^[15]

Traffic congestion is one of the most common phenomena in reality. Intuitively, traffic congestion is caused by an excess of network load. In other words, if the packet generation rate does not reach a critical value, traffic congestion will not occur. One of the main reasons for traffic congestion is that the packet cannot be transmitted in time due to the limited transmission capacity of node. In addition to longer traffic time, traffic congestion will also cause air pollution, increasing social costs and economic losses. Packets will accumulate indefinitely within the node if the congestion persists and the storage capacity of nodes is infinite. However, it is reasonable for a node to have limited storage capacity.^[16] Previous studies show that traffic congestion is more likely to occur on scale-free networks than homogeneous networks.^[17–21] Traffic capacity depends on routing strategy and network structure.^[22] In order to improve traffic capacity and alleviate traffic congestion, researchers have proposed many methods. Generally, there are two ways to improve traffic capacity: the soft strategy by improving the routing strategy^[23] and the hard strategy by changing underlying structure.^[24] Because the second way is complex and costly, it is necessary to investigate the appropriate routing strategy and to optimize the supply of transportation resources.^[25,26]

Dynamical network^[27] is an important part of complex networks, where the nodes move all the time. Because dynamical networks have no fixed network structure, the characteristics of traffic congestion is different from that of static networks. Since the relative position of the nodes on the static network is determined, no matter what routing strategy is adopted, the packets will always pass through a limited number of determined neighbor nodes when transmitted from the current node to the destination. Moreover, it is easy to identify the transmission path of a packet on the static network, the node where traffic congestion occurs is easy to be determine. However, for the dynamic network, because the location of its nodes is always changing, the transmission path of packets is difficult to be predicted and ascertained, and the specific location of traffic congestion is difficult to be determined. In order to improve the traffic capacity of dynamic transportation networks, Yang et al.^[28] combined geographical distance and local traffic information through a traffic-awareness parameter on an adaptive routing strategy.

In most researches on packet transmission, packets follow the first-in-first-out (FIFO) rule when transferred between nodes,^[29] and the ability of nodes to store packets is assumed to be infinite.^[27] Although the FIFO rule are used in most situations, such as store services, products through pipelines, etc., the average travel time of packets is long when the network is congested by this rule. Meanwhile, the storage capacity of nodes is usually limited in reality. In this paper, we introduce a dynamical network model with limited storage capacity. There are two more rules for buffering packets in each node, one is the last-in-first-out (LIFO) rule, and the other is the random-in-random-out (RIRO) rule. We adopt the adaptive routing strategy to improve the transmission ability of network. From terms of the packet generation probability, the tunable parameter, and the buffer size, similarities and differences among the LIFO rule, the RIRO rule, and the FIFO rule are analyzed. In recent studies of multilayer networks with limited storage capabilities, many interesting phenomena are observed, such as Braess’ paradox,^[30] and the slower is faster effect.^[31] In this study, the similar phenomenon to Braess’ paradox is also found in simulation by the LIFO rule and the RIRO rule. We also find that the RIRO rule does not cause congestion within a large buffer size range.

The structure of this paper is as follows. In Section 2, we introduce our network model and the traffic model in detail. In Section 3, we present the simulated phenomena and results, then analyze and discuss them in detail. In the last section, we present conclusions.

In this section, we simulate the packet transmission process of dynamical network by the FIFO rule, LIFO rule and RIRO rule. We set the size of the square region L = 10, the total number of nodes N = 1500, the communication radius of nodes r = 1, and the node delivery capacity C = 1. The moving speed of nodes v = 0.1. Each simulation runs T_m time step, and T_m = 1 × 10⁵.

Traffic flow refers to the number of packets that arrive at their destination on the network in the whole simulation process. From Fig. 1(a), one can see that at first, the traffic flow increases linearly with increasing the packet generation rate ρ, and then drops suddenly after reaching the peak by the FIFO rule and the RIRO rule. However, by the LIFO rule, the traffic flow decreases gradually after reaching the peak, and is greater than the traffic flow by the other two queue rules. The average travel time ⟨T⟩ is defined as the average of the time each packet elapsed from the generation to destination. From Fig. 1(b), one can see that the average travel time ⟨T⟩ is almost constant with increasing probability ρ and remains at a very small value, and then mutates to a maximum of nearly 0.22. After the peak value, ⟨T⟩ decreases linearly by the FIFO rule and the RIRO rule. The inset in Fig. 1(b) shows the change trend of the average travel time ⟨T⟩ with the increase of ρ by the LIFO rule. One can see that the value of ⟨T⟩ is much smaller than those by the other two queue rules.

Fig. 1.

Figure Option ViewDownloadNew Window

Fig. 1. (a) The traffic flow, (b) average travel time ⟨T⟩, (c) packet loss Λ, and (d) network density Φ as a function of the packet generation rate ρ in three different queue rules. The simulation parameters are N = 1500, L = 10, C = 1, r = 1, v = 0.1 h = 0.5 and B = 100 (The black solid line indicates the FIFO rule, the red solid line represents the LIFO rule, and the blue solid line represents the RIRO rule unless stated otherwise).

The packet loss Λ refers to the ratio of the number of packets that did not successfully reach the destination in simulation to the total number of packets that have been generated. We can see from Fig. 1(c) that no packets are lost in the system by all the three queue rules when the packet generation rate ρ is less than 0.2. When ρ > 0.2, the system starts to have packet lost, and the greater the packet generation rate, the more serious the packet loss Λ. The packet loss Λ by the LIFO rule is lower than those by the other two queue rules. The network density Φ is the ratio of the number of packets in the system at current time step to the network capacity N × B. From Fig. 1(d), we can see that when ρ < 0.2, network density Φ is close to 0, and then suddenly increases to close to 1.

Taking a comprehensive analysis of Fig. 1, we can see that all lines in the same subgraph show the same trend by the FIFO rule and the RIRO rule, but the line by the LIFO rule is relatively smooth and performs significantly better than the other two queue rules. We can also know that for all three queue rules, when the packet generation rate ρ < 0.2, the network is in an unblocked state. Because the number of generated packets does not meet the traffic capacity of the network when ρ < 0.2, traffic congestion will not occur, and traffic flow cannot reach its maximum. After about 0.2, the system starts to be congested, and the greater the ρ is, the more serious the congestion is. Because the number of generated packets exceeds the number that the network can transfer, the packets begin to accumulate in the nodes, causing traffic congestion and packets loss. In other words, traffic congestion begins at ρ ≈ 0.2.

Then we study the effect of tunable parameter h on the traffic capacity. We set ρ = 0.2 and B = 100 based on the result of Fig. 1. Figure 2(a) shows the trend of the traffic flow as a function of the tunable parameter h by different queue rules. The maximum traffic flow is close to 3 × 10⁷. In this state, the average traffic flow per time step of the network is close to 300. Since the network has 1500 nodes and the packet generation rate ρ = 0.2, the network generates an average of 300 packets per time step, so this is the maximum state of network traffic. In the maximum state of the traffic flow, the number of generated packets and the number of packets arrived at destinations are almost equal at each time step, the network will not be blocked, and the rest of the part indicates the traffic congestion. Compared to the maximum state by the FIFO rule, the unblocked state is within a larger range of h (around the interval [0.14, 0.93]) by the RIRO rule. The traffic flow by the LIFO rule does not occur phase transition with the change of h, and the traffic flow is larger than the traffic flow by the FIFO rule over the entire range of h.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. (a) The traffic flow, (b) average travel time ⟨T⟩, (c) packet loss Λ, and (d) the network density Φ versus the tunable parameter h. The simulation parameters are N = 1500, L = 10, C = 1, r = 1, v = 0.1, B = 100, and ρ = 0.2.

One can see from Fig. 2(b) that the average travel time ⟨T⟩ is very short within a large range of h (around the interval [0.14, 0.93]) by the RIRO rule compared to the FIFO rule. By the LIFO rule, the curve transformation is gentle and always at a low level, i.e., no phase transition occurs when the value of h is close to 0 or 1. The reason for this phenomenon is that regardless of the value of h, packets at the end of queues are always transmitted first, and can reach the destination quickly unless they are lost.

Figure 2(c) shows the packet loss Λ as a function of h. We can find that the trends of the curves in Figs. 2(c) and 2(a) are completely opposite. The reason is that when the network traffic flow is at the maximum, the number of packets in all the nodes will not exceed the buffer size, and packets at each node will not be lost. When the network traffic cannot reach the maximum value, the network is in a congestion state. Obviously, the higher the packet loss Λ, the more serious the traffic congestion, and the lower the traffic flow.

Figure 2(d) shows the network density Φ as a function of h. We can see that network density Φ exhibits two phase transitions with the change of h by the LIFO rule, which is significantly different from the traffic flow, average travel time and packet loss rate. From Fig. 2(d) we can clearly see that the range of h by the RIRO rule in traffic congestion is larger than those by the FIFO rule and the LIFO rule.

It can be seen from Fig. 2 that the tunable parameter h combining the Euclidean distance and the node state can effectively enhance the traffic capacity of the dynamical network.

Next, we set ρ = 0.2 and h = 0.5 to study the effect of the node buffer size B on traffic congestion according to the results of Fig. 2. From Fig. 3(a) we can see that the traffic flow by the FIFO rule increases when 0 < B ⩽ 25, then it decreases first and then increases sharply when 25 ⩽ B ⩽ 85, when 85 ⩽ B ⩽ 280, the traffic flow reaches its maximum and fluctuates slightly around it, then the traffic flow generally shows a rapid downward trend. The traffic flow by the LIFO rule increases linearly when 0 < B ⩽ 70, then the traffic flow reaches its maximum and fluctuates slightly around it until B = 505. Finally, the traffic flow continues to decrease slightly. For the RIRO rule, the traffic flow increases rapidly when 0 < B ⩽ 20. When 20 ⩽ B ⩽ 600, the traffic flow fluctuates slightly around its maximum.

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. (a) The traffic flow, (b) the network density Φ, and (c) packet loss Λ as a function of the node buffer size B. The simulation parameters are N = 1500, L = 10, C = 1, r = 1, v = 0.1, B = 100, and ρ = 0.2.

From Fig. 3(b), one can see that the network density Φ by the FIFO rule increases greatly until close to 1 when 0 < B ⩽ 85, then suddenly drops to nearly 0 and fluctuates around its minimum between B = 85 and B = 280, when B > 280, the network density Φ first increases to nearly 1 rapidly, and then fluctuates around its maximum. The network density Φ by the LIFO rule increases greatly when 0 < B ⩽ 65, then drops rapidly to the bottom when B = 75, and fluctuates slightly around its minimum when 75 < B ⩽ 505, finally rises slowly when B > 505. The network density Φ by the RIRO rule decreases rapidly first when 0 < B ⩽ 45, and then slowly decreases and slightly fluctuates around the minimum when B > 45.

In Fig. 3(c), the curves of the FIFO rule and the RIRO rule, respectively, are nearly the same and completely opposite to the lines in Fig. 3(a). However, there are no packets lost between B = 505 and B = 600 by the LIFO rule although the network is in a congestion state in this interval. The density of the system by the LIFO rule starts to rise slowly after B > 505, which explains that the number of packets entering nodes begins to be greater than those removed from nodes, but the queue length of packets in each node of the network has not exceeded the node buffer size. Therefore, there will be no packets lost temporarily.

As seen from Fig. 3, for the LIFO rule, when B is small, Φ increases, Λ decreases and the traffic flow increases, because the second term q_i(t)/B in Eq. (3) is mainly in this case. According to this routing strategy, a packet is transmitted to a neighbor node that is the shortest from its destination. Since B is very small, the increase or decrease of a packet will significantly change the value of q_i(t)/B and have a significant impact on the whole Eq. (3). At this point, these nodes are easy to be congested, packets will be lost, and the congestion state of the entire network appears. Because only a small number of nodes are congested, the density and packet loss of the network are not high. As B increases, the difference between the influences of the two terms of Eq. (3) is weakened, so the traffic flow increases and the packet loss decreases. After that, the trend of packet loss Λ by the LIFO rule is different from that by the FIFO rule, because most packets at the end of the queue are preferentially transferred out, avoiding being lost.

The trend of the network density Φ by the RIRO rule continues to decrease as B increases. At the beginning, the packets of a node are randomly transferred from the queue to a neighbor node with the shortest queue. The cause of the congestion is the same as the other two queue rules. As B increases, the effect of effective routing in Eq. (3) is enhanced. The random transfer of packets makes the packets in the queue not be backlogged in the nodes because their positions are too far back or too far ahead, so the network density will decrease with the node buffer size increasing, and the packet loss Λ decreases rapidly. When the node buffer size is too large, the second term q_i(t)/B in Eq. (3) is almost negligible, and the first one plays a major role. When the system starts running, packets will be transmitted to the neighbor nodes closest to these destinations, and make the queue of these neighbor nodes longer. However, these nodes are not sensitive to this change as the time step increases, and then all nodes, which originally had very few packets, get large number of packets due to the invalidation of the effective routes. When the queue of a node is too long, the packets cannot be transported out in time, and the network is inevitably congested.

For the LIFO rule, although congestion occurs at large values of B, the packets at the end of the queue in a node can be quickly transported away, avoiding the node capacity being filled quickly, so the network density Φ does not suddenly increase, and packets will not be lost. Obviously, the RIRO rule can better adapt to the situation of effective route failure.

Combined with Fig. 3 and Eq. (3), only when by two terms of Eq. (3) work at the same time, can the traffic capacity of the network be at its optimal. Therefore, for the FIFO rule, the suitable range of B should not be too large, for the LIFO rule, the suitable range of B is larger, for the RIRO rule, the suitable range of B is larger than the LIFO rule because of more flexible queue rules.

Figure 4 shows the trend of the average travel time ⟨T⟩ with the increase of node buffer size B. The inset of Fig. 4 shows the average travel time ⟨T⟩ by the FIFO rule, which behaves a phenomenon similar to Braess’ paradox. Braess’ paradox can be explained by the fact that in some cases, adding resources to a system will reduce its performance.

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. The average travel time ⟨T⟩ as a function of the node buffer size B. B2 and B3 are the critical values of phase change for the FIFO rule. B4 and B5 are the critical values of phase change for the LIFO rule. B6 is the critical value of phase change for the RIRO rule. The simulation parameters are N = 1500, L = 10, C = 1, r = 1, v = 0.1, B = 100, and ρ = 0.2.

When B < B₂ or B > B₃, the average travel time ⟨T⟩ increases with the increase of B. We can see from Fig. 3 that the network occurs traffic congestion in these two intervals, and many nodes have almost full buffer. Since the packets in front of a queue are transmitted first, the larger the buffer size, the more packets in nodes, the longer the waiting time of the packets in the queue, and the longer their average travel time for all packets, when B₂ ⩽ B ⩽ B₃, the network is in the unblocked state, the packets in the node do not accumulate, so the average travel time ⟨T⟩ is very small and keeps almost unchanged. The average travel time ⟨T⟩ by the LIFO rule also shows a phenomenon similar to Braess’ paradox when B < B₄ or B > B₅.

It is caused by the same reason as the FIFO rule, but the packets at the end of a queue are always transmitted preferentially, so the average travel time ⟨T⟩ is much less than that by the FIFO rule, when B₄ ⩽ B ⩽ B₅, according to Fig. 3. Since the network is unblocked, ⟨T⟩ is relatively smaller, but the number of packets in a node is increasing, the nodes at the front of the queue still need more waiting time, causing an increase in ⟨T⟩. ⟨T⟩ by the RIRO rule also shows a phenomenon similar to Braess’ paradox when B < B₆, and ⟨T⟩ decreases first and then slowly increases because of the unblocked state when B > B₆. We can also see from Fig. 4 that B₆ < B₄ < B₂, that is to say, the RIRO rule is more suitable than the FIFO rule and the LIFO rule to increase the input of capacity resources without worrying about the reduction of the effect.

In this paper, we apply three queue rules to a dynamic network with a finite buffer size and use an adaptive routing strategy to transport packets on the network. When the packet generation rate exceeds the critical value, traffic congestion is inevitable, but the average travel time by the LIFO rule is much smaller than the other two queue rules. The RIRO rule makes the network more adaptable to the wide range of the tunable parameter. This means that when using the FIFO rule, the choice of the tunable parameter should be more cautious. Then we find that the FIFO rule is the least adaptable to changes in the buffer size, and it only makes the network unblocked in a small buffer size range. In contrast, the RIRO rule is optimal. For the LIFO rule, no packets are lost when the buffer size just exceeds the threshold of network congestion. In addition, we also find a phenomenon similar to Braess’ paradox by the LIFO rule and the RIRO rule. When traffic congestion occurs, increasing the node buffer size within a certain range will not make the congestion disappear, but will make it serious and increase the average travel time of packets.

We believe that our work will provide a valuable reference for mitigating real-world traffic congestion. For example, when using a large number of drones for data storage and data relay transmission, the RIRO rule should be adopted to achieve the purpose of realizing rapid transmission of information and reducing the possibility of data loss, moreover, upgrading the storage capacity of these drones will not cause a significant reduction in data transmission efficiency.